package com.dyz.swordFingerOffer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;

public class Permutation38 {

    public static void main(String[] args) {
        String s = "abc";
        ArrayList<String> arr = new Permutation38().Permutation(s);
        System.out.println(arr);
    }
    //递归（字符交换）回溯
    public ArrayList<String> Permutation(String str) {

        char[]  a = str.toCharArray(); //将字符串转成字符数组
        ArrayList<String> ans = new ArrayList<>();

        dfs(ans, a, 0, str.length());
        //去重
        ans = new ArrayList<>(new HashSet<>(ans));
        //排序
        Collections.sort(ans);
        return ans;

    }
    private void dfs(ArrayList<String> ans, char[] a, int index, int length){
        System.out.println(index);
        //交换位置在最后一个，递归的终止条件，
        if (index==length-1){
            String res = change(a);
            ans.add(res);
        }else {
            //交换位置下标不是末尾， 就是说明现在要去确定index位置的字符
            for(int i = index; i<length; i++){
                char temp = a[i];
                a[i] = a[index];
                a[index] = temp;
                //当前inde位置的字符已经通过交换得到，那么就递归下一位位置
                dfs(ans, a, index+1, length);
                //其实就是去为了消除当前层去递归的时候的进行交换字符的影响
                temp = a[i];
                a[i] = a[index];
                a[index] = temp;
            }
        }
    }
    private String change(char[] a){
        //char[] 转为 string
        StringBuilder res = new StringBuilder();
        for (char value:a){
            res.append(value);
        }
        return res.toString();

    }
}
